public class Solution {
    public int longestValidParentheses(String s) {
        int maxLen = 0, last = -1;
        LinkedList<Integer> lefts = new LinkedList<>();

        for(int i = 0; i < s.length(); ++i) {
            if(s.charAt(i) == '(') {
                lefts.push(i);
            } else if(lefts.isEmpty()) {
                last = i;
            } else {
                lefts.pop();
                if(lefts.isEmpty()) {
                    maxLen = Math.max(maxLen, i - last);
                } else {
                    maxLen = Math.max(maxLen, i - lefts.peek());
                }
            }
        }
        return maxLen;
    }
}